We study the effects of approximate inference on the performance of Thompson sampling in the $k$-armed bandit problems. Thompson sampling is a successful algorithm for online decision-making but requires posterior inference, which often must be approximated in practice.

Thompson Sampling with Approximate Inference This paper investigates the performance of Thompson sampling, when the sampled distribution does not match the "problem" distribution exactly. The authors clearly explain some settings where mismatched sampling distributions can cause linear regret. The authors support their analysis with some expository "toy" experiments. There are several things to like about this paper: - This paper is one of the first to provide a clear analysis of Thompson sampling in the regime of imperfect inference. It seems like another solution that would "intuitively work" is to artificially expand the "prior" of the Thompson sampling procedure, but in a way that would concentrate away with data.

This submission was diligently evaluated, and the main problem that was identified was clarity. An additional expert reviewer was asked to checked the proofs. I am suggesting acceptance, given that the authors put a serious effort into rewriting. The reviewers did a great job in identifying where the improvements are needed, please do take advantage of that. Furthermore, for the final version, please take a look at this paper: https://link.springer.com/chapter/10.1007%2F978-3-319-46379-7_22 .

We study the effects of approximate inference on the performance of Thompson sampling in the k -armed bandit problems. Thompson sampling is a successful algorithm for online decision-making but requires posterior inference, which often must be approximated in practice. We show that even small constant inference error (in \alpha -divergence) can lead to poor performance (linear regret) due to under-exploration (for \alpha 1) or over-exploration (for \alpha 0) by the approximation. While for \alpha 0 this is unavoidable, for \alpha \leq 0 the regret can be improved by adding a small amount of forced exploration even when the inference error is a large constant.

We study the effects of approximate inference on the performance of Thompson sampling in the $k$-armed bandit problems. Thompson sampling is a successful algorithm for online decision-making but requires posterior inference, which often must be approximated in practice. We show that even small constant inference error (in $\alpha$-divergence) can lead to poor performance (linear regret) due to under-exploration (for $\alpha 1$) or over-exploration (for $\alpha 0$) by the approximation. While for $\alpha 0$ this is unavoidable, for $\alpha \leq 0$ the regret can be improved by adding a small amount of forced exploration even when the inference error is a large constant. Papers published at the Neural Information Processing Systems Conference.